1. Field of the Invention
This invention relates to a block encryption system and more particularly to a method and apparatus for encrypting a long plaintext block using an encryption procedure intended for relatively short blocks.
1. Description of the Related Art
Encryption schemes fall into two general categories: symmetric encryption systems and asymmetric encryption systems. In symmetric encryption systems, such as those conforming to the Data Encryption Standard (DES), the same key is used by the originator to encrypt data (i.e., convert plaintext to ciphertext) and by the recipient to decrypt the same data (i.e., convert ciphertext back to ciphertext). Symmetric encryption schemes can often be implemented very efficiently, but suffer the disadvantage of requiring the prior exchange of encryption keys over a secure communications channel.
Asymmetric encryption systems, or public key encryption systems as they are usually called, use one key to encrypt data while using another key to decrypt the same data. In a public key encryption system, an intended recipient of data generates a key pair consisting of an encryption key, which is made public, and a corresponding decryption key, which is kept private and not shared with others. The keys are generated in such a manner that the private key cannot be derived from knowledge of the corresponding public key; hence, only the intended recipient having the private key decrypt a ciphertext message generated using the public key. An important advantage public key encryption systems have over symmetric systems is that they do not require the exchange of secret key information; two parties can establish a secure two-way communication by exchanging public keys that they have generated. For this reason, asymmetric encryption systems are often used for the secret key exchange required in symmetric encryption systems.
Perhaps the most well-known public key encryption system is the RSA encryption system, named after its originators and described in R. L. Rivest et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21, no. 2, pp. 120-126 (1978). RSA encryption systems typically have encryption blocks on the order of 512 bits and can be computationally quite intensive. Recently, however, so-called elliptic curve systems have been described in such references as N. Koblitz, "Elliptic Curve Cryptosystems", Mathematics of Computation, vol. 48, no. 177, pp. 203-209(January 1987), and A. Menezes, Elliptic Curve Public Key Cryptosystems (1993). Like the RSA encryption system, elliptic curve systems are public key systems with public encryption keys and private decryption keys. Elliptic curve systems typically have relatively short key and encryption block sizes, on the order of 160 bits for each, but have a cryptographic strength that is comparable to that of longer block RSA encryption systems. Elliptic curve systems thus represent an attractive combination of cryptographic strength and computational efficiency.
Since elliptic curve encryption systems are public key systems, one use of such systems might be to distribute keys. Thus, user A might use a public elliptic curve key to encrypt a symmetric key (e.g., a DES key) for distribution to user B. But a problem arises, since the symmetric key is normally contained in a key block (e.g., a 512-bit block) which is much longer than the elliptic curve encryption block, which, as noted above, may be on the order of only 160 bits. Although the key block can be divided into multiple encryption blocks of sufficiently small size, the additional encryption operations required for the individual encryption blocks vitiate to some extent the natural advantages of elliptic curve systems in terms of their computational efficiency. What is needed is a method of key encryption that can be used with an elliptic curve algorithm which will permit a large key block to be encrypted with a secret elliptic curve key of much shorter length.